package org.example.day01;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO +
 * 宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。
 * 游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。
 * 请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。
 * @date 2024/3/11 15:21
 */
public class test001 {
    static final int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] grid = new int[n][n];
        int[] mom = new int[2];
        int[] baby = new int[2];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = scanner.nextInt();
                if (grid[i][j] == -2) baby = new int[]{i, j};
                if (grid[i][j] == -3) mom = new int[]{i, j};
            }
        }

        int maxCandies = bfs(grid, mom, baby, n);
        System.out.println(maxCandies);
    }

    // 广度优先搜索函数
    private static int bfs(int[][] grid, int[] start, int[] end, int n) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{start[0], start[1], 0, 0}); // [x, y, 步数, 糖果数]
        int[][][] visited = new int[n][n][2]; // 记录步数和糖果数
        for (int[][] rows : visited) {
            for (int[] cell : rows) {
                Arrays.fill(cell, -1);
            }
        }
        visited[start[0]][start[1]][0] = 0;
        visited[start[0]][start[1]][1] = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0], y = current[1], steps = current[2], candies = current[3];

            for (int[] dir : directions) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                if (isValid(nx, ny, n, grid)) {
                    int newCandies = candies + Math.max(grid[nx][ny], 0);
                    if (visited[nx][ny][0] == -1 || visited[nx][ny][0] > steps + 1
                            || (visited[nx][ny][0] == steps + 1 && visited[nx][ny][1] < newCandies)) {
                        visited[nx][ny][0] = steps + 1;
                        visited[nx][ny][1] = newCandies;
                        queue.offer(new int[]{nx, ny, steps + 1, newCandies});
                    }
                }
            }
        }
        return visited[end[0]][end[1]][1];
    }

    // 检查坐标是否有效
    private static boolean isValid(int x, int y, int n, int[][] grid) {
        return x >= 0 && x < n && y >= 0 && y < n && grid[x][y] != -1;
    }
}
